852D - Exploration plan - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db long double
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b / __gcd(a,b)
#define I first
#define II second
#define pb push_back
#define ii pair<int,int>
const int INF = 2 * 1e9;
const int N = 600 + 1;
const int MOD = 1e9 + 7;
int n, k, v, e, d[N][N], mv[N], vs[N], a[N], ans;
set<ii> q;
vector<ii> g[N];
vector<int> g1[N];
int dfs(int u)
{
    for (int v : g1[u])
        if (!vs[v])
    {
        if (!mv[v])
        {
            mv[v] = u;
            return 1;
        }
        vs[v] = 1;
        if (dfs(mv[v]))
        {
            mv[v] = u;
            return 1;
        }
    }
    return 0;
}
bool check(int t)
{
    for (int i = 1; i <= v; i++) g1[i].clear(), mv[i] = vs[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= v; j++)
            if (d[i][j] <= t) g1[i].pb(j);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= v; j++) vs[j] = 0;
        cnt += dfs(i);
    }
    return (cnt >= k);
}
int tknp(int l, int r)
{
    while (l + 1 < r)
    {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid; else l = mid + 1;
    }
    if (check(l)) return l;
    return r;
}
int main()
{
#define TASKNAME "lucky"
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(TASKNAME".inp","r" ))
    {
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> v >> e >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (e --)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= v; j++) d[i][j] = INF;
        d[i][a[i]] = 0;
        q.insert({0, a[i]});
        while (!q.empty())
        {
            auto [dmn, u] = *q.begin();q.erase(q.begin());
            if (dmn != d[i][u]) continue;
            for (auto [v, w] : g[u])
                if (d[i][v] > d[i][u] + w)
            {
                d[i][v] = d[i][u] + w;
                q.insert({d[i][v], v});
            }
        }
    }
    ans = tknp(0, 1731311);
    cout << (check(ans) ? ans : -1);
    return 0;
}